//===----------------------------------------------------------------------===//
//
//                         BusTub
//
// lru_k_replacer.cpp
//
// Identification: src/buffer/lru_k_replacer.cpp
//
// Copyright (c) 2015-2022, Carnegie Mellon University Database Group
//
//===----------------------------------------------------------------------===//

#include "buffer/lru_k_replacer.h"
#include <algorithm>
#include "common/exception.h"

namespace bustub {

LRUKReplacer::LRUKReplacer(size_t num_frames, size_t k)
    : node_store_({}), current_timestamp_{1}, k_(k), lru_sub_list_({}), k_level_map_({}) {}

auto LRUKReplacer::Evict(frame_id_t *frame_id) -> bool {
  // Choose a frame for victim, simply delete it from priority_queue, remeber not directly delete reference histories
  latch_.lock();
  if (!lru_sub_list_.empty()) {
    frame_id_t victim = lru_sub_list_.back();
    lru_sub_list_.pop_back();
    *frame_id = node_store_[victim].fid_;
    node_store_.erase(victim);
    evictable_--;
    latch_.unlock();
    return true;
  }
  size_t min = current_timestamp_++;
  size_t now = min;
  auto res = k_level_map_.end();
  auto it = k_level_map_.begin();
  auto end = k_level_map_.end();
  for (; it != end; it++) {
    frame_id_t frame = it->first;
    LRUKNode &node = node_store_[frame];
    if (node.is_evictable_ && now - node.GetLast() > crp_ && node.GetHistory(k_) <= min) {
      min = node.GetHistory(k_);
      res = it;
    }
  }
  if (res != k_level_map_.end()) {
    *frame_id = res->first;
    node_store_.erase(res->first);
    k_level_map_.erase(res);
    evictable_--;
    latch_.unlock();
    return true;
  }
  latch_.unlock();
  return false;
}

void LRUKReplacer::RecordAccess(frame_id_t frame_id, [[maybe_unused]] AccessType access_type) {
  latch_.lock();
  if (node_store_.find(frame_id) != node_store_.end()) {
    // Frame is already in buffer
    size_t time_now = current_timestamp_++;
    LRUKNode &node = node_store_[frame_id];
    if (time_now - node.last_reference_ > crp_) {
      // new uncorrelated reference
      node.history_.push_front(node.last_reference_);
      node.last_reference_ = time_now;
      if (node.k_ == k_) {
        node.history_.pop_back();
      } else {
        node.k_++;
        if (node.k_ == k_) {
          lru_sub_list_.remove(frame_id);
          k_level_map_[frame_id] = true;
        }
      }
    } else {
      node.last_reference_ = time_now;
    }
  } else {
    LRUKNode node{};
    node.fid_ = frame_id;
    node.is_evictable_ = true;
    node.k_ = 1;
    node.last_reference_ = current_timestamp_++;
    node_store_[frame_id] = node;
    lru_sub_list_.push_front(frame_id);
    evictable_++;
  }
  latch_.unlock();
}

void LRUKReplacer::SetEvictable(frame_id_t frame_id, bool set_evictable) {
  latch_.lock();
  if (node_store_.find(frame_id) == node_store_.end()) {
    throw std::logic_error("Frame id is invalid");
  }
  if (node_store_[frame_id].is_evictable_ && !set_evictable) {
    evictable_--;
    node_store_[frame_id].is_evictable_ = false;
    if (node_store_[frame_id].k_ < k_) {
      lru_sub_list_.remove(frame_id);
    } else {
      k_level_map_.erase(frame_id);
    }
  } else if (!node_store_[frame_id].is_evictable_ && set_evictable) {
    evictable_++;
    node_store_[frame_id].is_evictable_ = true;
    if (node_store_[frame_id].k_ < k_) {
      lru_sub_list_.push_front(frame_id);
    } else {
      k_level_map_[frame_id] = true;
    }
  }
  latch_.unlock();
}

void LRUKReplacer::Remove(frame_id_t frame_id) {
  latch_.lock();
  if (node_store_.find(frame_id) != node_store_.end()) {
    if (!node_store_[frame_id].is_evictable_) {
      throw std::logic_error("Attempt to remove a non-evicttable frame...");
    }
    if (node_store_[frame_id].k_ < k_) {
      lru_sub_list_.remove(frame_id);
    } else {
      k_level_map_.erase(frame_id);
    }
    evictable_--;
    node_store_.erase(frame_id);
  }
  latch_.unlock();
}

auto LRUKReplacer::Size() -> size_t {
  latch_.lock();
  size_t ret_val = evictable_;
  latch_.unlock();
  return ret_val;
}

}  // namespace bustub
